package _06_动态规划;

/**
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @Author: haogege
 * @Date: 2021/8/31
 */
public class _5_最长回文子串 {

    public static void main(String[] args) {
        _5_最长回文子串 v = new _5_最长回文子串();
        System.out.println(v.longestPalindrome("abba"));

    }

    // 马拉车算法 Manacher
    public String longestPalindrome(String s) {
        if (s == null) return null;
        if (s.length() == 1) return s;
        char[] chars = s.toCharArray();
        // 构造马拉车数据
        char[] newChars = process(chars);
        // 构建m数组
        int[] m = new int[newChars.length];
        int idx = 0;
        int len = 0;
        int c = 1;
        int r = 1;
        int lastIndex = newChars.length - 2;
        // 遍历元素
        for (int i = 2; i < lastIndex; i++) {
            if (r > i) {
                int li = (c << 1) - i;
                m[i] = (i + m[li] <= r)? m[li]: (r - i);
            }

            // 中心扩展寻找
            while (newChars[i + m[i] + 1] == newChars[i - m[i] - 1] ) {
                m[i]++;
            }

            // 更新c， r

            if (i + m[i] > r) {
                c = i;
                r = i + m[i];
            }

            if (m[i] > len) {
                len = m[i];
                idx = i;
            }
        }
        return new String(chars, (idx - len) >> 1, len);
    }

    private char[] process(char[] chars) {
        char[] newChars = new char[(chars.length << 1) + 3];
        newChars[0] = '^';
        newChars[1] = '#';
        newChars[newChars.length - 1] = '$';

        for (int i = 0; i < chars.length; i++) {
            int index = (i + 1) << 1;
            newChars[index] = chars[i];
            newChars[index + 1] = '#';
        }
        return newChars;
    }

    // 扩展中心法(以连续字符作为扩展中心)
    public String longestPalindromeEx(String s) {
        if (s == null) return null;
        if (s.length() == 1) return s;
        char[] chars = s.toCharArray();
        int begin = 0;
        int len = 1;
        int i = 0;
        while (i < chars.length) {
            int l = i - 1;
            // 寻找左边第一个不等于chars[i]的字符
            int r = i;
            while (++r < chars.length && chars[r] == chars[i]);
            i = r;

            while (l >= 0 && r < chars.length && chars[l] == chars[r]) {
                l--;
                r++;
            }

            int maxLen = r - ++l;
            if (maxLen > len) {
                len = maxLen;
                begin = l;
            }
        }
        return new String(chars, begin, len);
    }

    // 扩展中心法
    public String longestPalindromeEx1(String s) {
        if (s == null) return null;
        if (s.length() == 1) return s;
        char[] chars = s.toCharArray();
        int begin = 0;
        int len = 1;
        for (int i = chars.length - 2; i > 0; i--) {
            // 以当前字符为扩展节点
            int len1 = palindromeLen(chars, i - 1, i + 1);
            // 以当前字符右间隙为扩展中心
            int len2 = palindromeLen(chars, i, i + 1);
            // 取最大len
            int maxLen = Math.max(len1, len2);
            if (maxLen > len) {
                len = maxLen;
                begin = i - ((maxLen - 1) >> 1);
            }
        }

        // 计算最后一个
        if (chars[0] == chars[1] && len < 2) {
            len = 2;
            begin = 0;
        }
        return new String(chars, begin, len);
    }

    private int palindromeLen(char[] chars, int left, int right) {
        while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }


    // dp数组优化
    public String longestPalindromeDp(String s) {
        if (s.length() == 1) return s;
        char[] chars = s.toCharArray();
        boolean[] dp = new boolean[chars.length];
        // 记录开始索引
        int begin = 0;
        // 记录最大长度
        int maxLen = 1;
        for (int i = chars.length - 1; i >= 0; i--) {
            boolean cur = true;
            for (int j = i; j < chars.length; j++) {
                boolean leftBot = cur;
                cur = dp[j];
                int len = j - i + 1;
                dp[j] = (chars[i] == chars[j]) && (len <= 2 || leftBot);
                if (len > maxLen && dp[j]) {
                    // 更新
                    maxLen = len;
                    begin = i;
                }
            }
        }
        return new String(chars, begin, maxLen);
    }

    public String longestPalindromeDp1(String s) {
        if (s.length() == 1) return s;
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];
        // 记录开始索引
        int begin = 0;
        // 记录最大长度
        int maxLen = 1;
        for (int i = chars.length - 1; i >= 0; i--) {
            for (int j = i; j < chars.length; j++) {
                int len = j - i + 1;
                dp[i][j] = (chars[i] == chars[j]) && (len <= 2 || dp[i + 1][j - 1]);
                if (len > maxLen && dp[i][j]) {
                    // 更新
                    maxLen = len;
                    begin = i;
                }
            }
        }
        return new String(chars, begin, maxLen);
    }

}
